package cn.yuemouren.tree.segment;


/**
 * @Author: Timi
 * @Description: 线段树
 *              经过推倒 n个元素需要 4n 个数组长度
 * @Date: 2020/7/8 20:54
 * @Version: v1.0
 */
public class SegmentTree<T> {

    private T[] data;
    private T[] tree;
    private SegmentMerge<T> merge;

    public SegmentTree(T[] arr,SegmentMerge<T> merge){
        this.merge = merge;
        this.data = (T[])new Object[arr.length];
        for (int i = 0; i < data.length; i++){
            data[i] = arr[i];
        }
        this.tree = (T[])new Object[4 * arr.length];
        buildSegmentTree(0,0,data.length - 1);
    }

    /**
     * 构建线段树
     * @param treeIndex
     * @param left
     * @param right
     */
    private void buildSegmentTree(int treeIndex,int left,int right){
        if(right == left){
            tree[treeIndex] = data[left];
            return;
        }
        int leftIndex = leftChild(treeIndex);
        int rightIndex = rightChild(treeIndex);
        int mid = left + (right - left) / 2;
        buildSegmentTree(leftIndex,left,mid);
        buildSegmentTree(rightIndex,mid + 1,right);

         tree[treeIndex] = merge.merge(tree[leftIndex],tree[rightIndex]);
    }

    /**
     * 查询区间[queryLeft-queryRight]之间的值
     * @param queryLeft
     * @param queryRight
     * @return
     */
    public T query(int queryLeft,int queryRight){
        if(queryLeft < 0 || queryLeft >= data.length || queryRight < 0
                || queryRight >= data.length || queryLeft > queryRight){
            throw new IllegalArgumentException("index is fail.");
        }
        return  query(0,0,data.length-1,queryLeft,queryRight);
    }

    /**
     *  查询区间值
     * @param treeIndex
     * @param left 区间开始
     * @param right 区间结束
     * @param queryLeft
     * @param queryRight
     * @return
     */
    private T query(int treeIndex,int left,int right,int queryLeft,int queryRight){
        if(left == queryLeft && right == queryRight){
            return tree[treeIndex];
        }

        int leftIndex = leftChild(treeIndex);
        int rightIndex = rightChild(treeIndex);
        int mid = left + (right-left) / 2;

        if(queryLeft >= mid + 1){
            return query(rightIndex,mid + 1,right,queryLeft,queryRight);
        } else if(queryRight <= mid){
            return query(leftIndex,left,mid,queryLeft,queryRight);
        }

        T leftQuery = query(leftIndex, left, mid, queryLeft, mid);
        T rightQuery = query(rightIndex, mid + 1, right, mid + 1, queryRight);
        return merge.merge(leftQuery,rightQuery);
    }

    public void set(int index,T t){
        if(index < 0 || index >= data.length)
            throw new IllegalArgumentException("index is fail.");
        set(0,0,data.length-1,index,t);
    }

    private void set(int treeIndex,int left,int right,int index,T t){
         if(left == right){
             tree[treeIndex] = t;
             return;
         }

         int mid = left + (right - left) / 2;

         int leftChild = leftChild(treeIndex);
         int rightChild = rightChild(treeIndex);

         if(index >= mid + 1){
             set(rightChild,mid + 1,right,index,t);
         } else{
             set(leftChild,left,mid,index,t);
         }

         tree[treeIndex] = merge.merge(tree[leftChild],tree[rightChild]);
    }

    public int size(){
        return data.length;
    }

    public T get(int index){
        if(index < 0 || index >= data.length){
            throw new IllegalArgumentException("index is fail.");
        }
        return data[index];
    }

    /**
     * 获取左孩子索引
     * @param index
     * @return
     */
    private int leftChild(int index){
        return 2 * index + 1;
    }

    /**
     * 获取右孩子索引
     * @param index
     * @return
     */
    private int rightChild(int index){
        return 2 * index + 2;
    }
}
